#include <stdint.h>
#include "uint128.h"

uint128_t uint128_div_v0_bitbybit(uint128_t n, uint128_t d) 
{
    uint128_t t;
    int shift;
    
    //------ case 1: n<d, return 0----------
    if ( __builtin_sub_overflow(n,d,&t))
    {   
        return 0;
    }
    
    union
    {
        uint128_t tu;
        uint64_t  du[2];
    } _n = {n};
    
    union
    {
        uint128_t tu;
        uint64_t  du[2];
    } _d = {d};

    //--------- case 2:  do div XX/YY,q=XX/YY<2^64 --------
    if ( _d.du[1] ) // d>=2^64
    {
        shift = (64-__builtin_clzl(_n.du[1]))-(64-__builtin_clzl(_d.du[1]));
        _d.tu <<= shift;
        shift++;
        uint64_t q=0;
        while (shift>0)
        {
            uint64_t mask= 0ul -  __builtin_sub_overflow(_n.tu,_d.tu,&t);
            q= (q<<1) | (mask+1);
            // if _n<_d, then mask=-1, keep _n don't change, 
            // else mask=0, set _n= _n -d 
            if ( !mask) 
               _n.tu=t;
            _d.tu >>= 1;
            shift--;
        }
        return (uint128_t)q;
    }
    
    //------ case 3:  do div XX/0Y,q = XX/0Y <2^128 -----------
    if ( _n.du[1] ) // n>=2^64
    {
        union
        {
            uint128_t tu;
            uint64_t  du[2];
        } q = {0};
        
        shift = (128-__builtin_clzl(_n.du[1]))-(64-__builtin_clzl(_d.du[0]));
        _d.tu <<= shift;
        shift++;
        while (shift>0)
        {
            uint64_t mask= 0ul -  __builtin_sub_overflow(_n.tu,_d.tu,&t);
            q.tu <<=1;
            q.du[0] |= (mask+1);
            // if _n<_d, then mask=-1, keep _n don't change, 
            // else mask=0, set _n= _n -d 
            if ( !mask) 
               _n.tu=t;
            _d.tu >>= 1;
            shift--;
        }
        return q.tu;
    }
    
    //-------- case 4:  do div 0X/0Y,q = 0X/0Y <2^64  ----------------
    uint64_t q  = 0;
    uint64_t n0 = _n.du[0];
    uint64_t d0 = _d.du[0];
    uint64_t t0;
    shift = (64-__builtin_clzl(n0))-(64-__builtin_clzl(d0));
    d0 <<= shift;
    shift++;
    while (shift>0)
    {
        uint64_t mask= 0ul - __builtin_usubl_overflow(n0,d0,&t0);
        q = (q<<1) | (mask+1);
        // if _n<_d, then mask=-1, keep _n don't change, 
        // else mask=0, set _n= _n -d
        if ( !mask) 
            n0=t0;
        d0 >>= 1;
        shift--;
    }
    return (uint128_t)q;
}

